package top.jafar.data.structures;

import java.util.Scanner;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();
        list.add(1);
        list.add(3);
        list.add(5);
        list.add(7);
        list.add(9);
        SingleLinkedList<Integer> list1 = new SingleLinkedList<>();
        list1.add(2);
        list1.add(10);
        list1.add(6);
        list.showList();
        list.concat(list1);
        list.showList();
    }
}

class SingleLinkedList<T> {
    private LinkedNode head;
    private int size;

    public boolean isEmpty() {
        return head == null;
    }

    public void add(T obj) {
        LinkedNode<T> node = new LinkedNode<>(obj);
        size++;
        if (isEmpty()) {
            head = node;
            return;
        }
        LinkedNode<T> tempNode = head;
        while (true) {
            if (tempNode.getNext() == null) {
                tempNode.setNext(node);
                break;
            }
            tempNode = tempNode.getNext();
        }
    }

    public void concat(SingleLinkedList<T> otherList) {
        LinkedNode otherTempNode = otherList.head;
        while (otherTempNode != null) {
            LinkedNode otherNextNode = otherTempNode.next;
            Comparable value = (Comparable) otherTempNode.getValue();
            LinkedNode innerTempNode = head;
            while (innerTempNode != null) {
                Comparable innerVal = (Comparable) innerTempNode.getValue();
                LinkedNode innerNextNode = innerTempNode.next;
                boolean rightGtable = innerNextNode == null ? true : ((Comparable) innerNextNode.getValue()).compareTo(value) > 0;
                if (innerVal.compareTo(value) < 0 && rightGtable) {
                    innerTempNode.next = otherTempNode;
                    otherTempNode.next = innerNextNode;
                    break;
                }
                innerTempNode = innerNextNode;
            }
            otherTempNode = otherNextNode;
        }
    }

    public void remove(T obj) {
        LinkedNode<T> tempNode = head;

        if (isEmpty()) {
            return ;
        }

        // 如果是头结点
        if (tempNode.getValue().equals(obj)) {
            size--;
            head = tempNode.getNext();
            return;
        }

        while (true) {

            if (tempNode.getNext().getValue().equals(obj)) {
                size--;
                tempNode.setNext(tempNode.getNext().getNext());
                break;
            } else if (tempNode.getNext() == null) {
                break;
            }
            tempNode = tempNode.getNext();
        }
    }

    public int size() {
        return size;
    }

    public T getHeadValue() {
        return head == null ? null : (T) head.getValue();
    }

    public void showList() {
        LinkedNode<T> tempNode = head;
        System.out.print("[");
        while (true) {
            System.out.print(tempNode.getValue()+", ");
            if (tempNode.getNext() == null) {
                break;
            }
            tempNode = tempNode.getNext();
        }
        System.out.println("]");
    }

    public void reverse() {
        if (size < 2) {
            return;
        }
//        LinkedNode<T> tempNode = head;
//        // 翻转时需要注意，节点之间的next可能会携带其下面的引用，建议重新生成一个节点
//        LinkedNode<T> reverseHead = new LinkedNode(head.getValue());
//        while (true) {
//            LinkedNode<T> nextNode = tempNode.getNext();
//            if (nextNode == null) {
//                break;
//            }
//            LinkedNode tempNextNode = new LinkedNode(nextNode.getValue());
//            tempNextNode.setNext(reverseHead);
//            reverseHead = tempNextNode;
//            tempNode = tempNode.getNext();
//        }
        LinkedNode reverseHead = head;
        LinkedNode cur = head.next;
        LinkedNode next;
        reverseHead.setNext(null);
        while (cur != null) {
            next = cur.next;
            cur.setNext(reverseHead);
            reverseHead = cur;
            cur = next;
        }
        head = reverseHead;
    }

    public class LinkedNode<T> {
        private T value;
        private LinkedNode next;

        public LinkedNode(T value) {
            this.value = value;
        }

        public T getValue() {
            return value;
        }

        public void setValue(T value) {
            this.value = value;
        }

        public LinkedNode getNext() {
            return next;
        }

        public void setNext(LinkedNode next) {
            this.next = next;
        }

        @Override
        public String toString() {
            return "LinkedNode{" +
                    "value=" + value + ", next="+next.getValue()+
                    '}';
        }
    }
}
